package com.jdaw.datastructure.search;

import java.util.ArrayList;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr={1,8,10,89,1000,1000,1000,1324};
        System.out.println(binarySearch2(arr,0,arr.length-1,1000));
    }

    public static int binarySearch(int[] arr,int left,int right,int findVal){
        //没有找到的情况
        if(left>right){
            return -1;
        }

        int mid=(left+right)/2;
        if(arr[mid]<findVal){
            return binarySearch(arr,mid+1,right,findVal);
        }else if(arr[mid]>findVal){
            return binarySearch(arr,left,mid-1,findVal);
        }else {
            return mid;
        }
    }

    public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal){
        //没有找到的情况
        if(left>right){
            return new ArrayList<Integer>();
        }

        int mid=(left+right)/2;
        if(arr[mid]<findVal){
            return binarySearch2(arr,mid+1,right,findVal);
        }else if(arr[mid]>findVal){
            return binarySearch2(arr,left,mid-1,findVal);
        }else {
            ArrayList<Integer> resIndexList = new ArrayList<Integer>();
            //向左边扫描
            int temp=mid-1;
            while(true){
                if(temp<0||arr[temp]!=findVal){
                    break;
                }
                resIndexList.add(temp);
                temp-=1;
            }
            resIndexList.add(mid);

            //向右扫描
            temp=mid+1;
            while(true){
                if(temp>arr.length-1||arr[temp]!=findVal){
                    break;
                }
                resIndexList.add(temp);
                temp+=1;
            }

            return resIndexList;
        }
    }
}
